class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def is_valid(segment):
            """
            验证IP段是否有效
            :param segment: 待验证的IP段
            :return: 是否有效
            """
            # 长度检查：IP段长度不能超过3
            if len(segment) > 3:
                return False
            # 前导零检查：不允许前导零，除非是单个0
            if len(segment) > 1 and segment[0] == '0':
                return False
            # 数值范围检查：必须在0-255之间
            return 0 <= int(segment) <= 255

        def backtrack(start, parts):
            """
            回溯函数
            :param start: 当前处理位置
            :param parts: 已经找到的有效IP段列表
            """
            # 终止条件1：找到4个有效段且用完了所有字符
            if len(parts) == 4 and start == len(s):
                result.append('.'.join(parts))
                return
            
            # 终止条件2：已经有4个段但还没用完字符，或已用完字符但还不到4个段
            if len(parts) == 4 or start == len(s):
                return
            
            # 尝试当前字符开始的1-3个字符作为IP段
            for length in range(1, 4):
                # 确保不会越界
                if start + length <= len(s):
                    # 获取当前段
                    segment = s[start:start + length]
                    # 如果当前段有效
                    if is_valid(segment):
                        # 将当前段加入结果
                        parts.append(segment)
                        # 递归处理下一段
                        backtrack(start + length, parts)
                        # 回溯：移除当前段，尝试其他可能
                        parts.pop()

        # 存储所有有效的IP地址
        result = []
        # 从字符串开始位置开始回溯
        backtrack(0, [])
        return result 